{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "b2dc1832",
   "metadata": {},
   "source": [
    "# 搜索算法\n",
    "## 搜索定义\n",
    "1. 从元素集合中找到某个特定元素的算法过程；\n",
    "2. 搜索过程通常返回True或False，分别表示元素是否存在。\n",
    "- PS: 有时，可以修改搜索过程，使其返回目标元素的位置。\n",
    "\n",
    "## 顺序搜索\n",
    "- 集合中的数据项彼此存在线性或顺序的关系，通过这种关系进行搜索——顺序搜索\n",
    "- Python的list因为下标是有序的，所以能够顺序访问，由此可以进行顺序搜索。\n",
    "- 顺序搜索对无序和有序列表的复杂度是相同的；但是搜索有序是比较快的"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "143d8f23",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 无序列表的顺序搜索;沿着索引向下走，知道索引结束 or 找出元素\n",
    "def search_unorderlist(alist,item):\n",
    "    pos = 0\n",
    "    found = False\n",
    "    while pos< len(alist) and not found:\n",
    "        if alist[pos] == item:\n",
    "            found = True\n",
    "        else:\n",
    "            pos = pos+1\n",
    "    return found\n",
    "\n",
    "# 有序搜索；增加一条，当item不满足XX规则，搜索结束——节约搜索时间【在找不到时】\n",
    "# [找得到的话与无序一样快]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2768c134",
   "metadata": {},
   "source": [
    "# 二分搜索\n",
    "- 二分搜索：选择位置为n/2的元素，将左右拆开。判断目标是在左边还是右边；一直二分，知道找到元素；\n",
    "- 特点：\n",
    "    - 顺序的复杂度是n,而二分的复杂是logn；\n",
    "    - 但当n过于小的时候，二分的效率反而不如顺序\n",
    "    - 且二分只适用顺序列表，排序算法也会影响效率【显然顺序搜索不需要排序，只是有序更好找而已】\n",
    "\n",
    "1. 二分搜索只适用于有序列表 【比如在降序列表中，左边是大的，而右边是小的】\n",
    "2."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "60184372",
   "metadata": {},
   "source": [
    "# 散列搜索/hash搜索\n",
    "\n",
    "##  hash table（哈希表/散列表）：它是一种数据存储结构，通常用来存储多个元素\n",
    "    1. 大部分场景下，哈希表以数据为基础构建。——hash table也是一种数据存储结构 \n",
    "    2. 每个存到哈希表中的元素，都有一个唯一对应关系（索引/键）。\n",
    "    3. 使用哈希表查处时，我们可以凭接该元素的对应关系直接找到它，无须遍历整个哈希表。\n",
    "    4. hash table 与其他存储结构（线性表，树等）相比，通过hash table找出目标元素效率十分高。\n",
    "    5. 但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了\"冲突\"，\n",
    " \n",
    "##  hash slot（哈希槽）：哈希表中每个位置通常被称作槽；\n",
    "    1. 槽通常用从零开始的整数进行编号；\n",
    "    2. 当哈希表中没有元素时，每个槽都是空的；【初始化为空None】\n",
    "    3. 【一般在构建哈希表时，先给到槽的数目，再确定h函数】\n",
    "\n",
    "\n",
    " \n",
    "##  h函数（哈希函数）：通过某种规则，使得关键字适度的分散在指定大小的顺序结构（哈希表）中。\n",
    "    1. 关键字越分散，时间复杂度越小，空间复杂度越高。【用空间换时间】\n",
    "    2. 常见的哈希函数——取余函数【用取余值做哈希值】【所以哈希表的槽数目＝取余数-1】；\n",
    " \n",
    "  \n",
    "##  λ（占用率\\载荷因子）： λ= 元素个数/散列表大小\n",
    "\n",
    "\n",
    "## 解决冲突方法：开放地址法、链地址法\n",
    "1. 开放定址法（线性探测）：遍历散列表，不断往回检查第一个槽，它尝试在散列表中寻找下一个空槽或地址。由于是逐个访问槽，\n",
    "    1. 线性探测有个缺点，那就是会使散列表中的元素出现聚集现象。\n",
    "2. 链接法：让每个槽有一个指向元素集合（或链表）的引用。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "517cde4e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 哈希表构建\n",
    "\n",
    "\n",
    "\n",
    "class HashTable:\n",
    "    def __init__(self):\n",
    "        self.size = 11\n",
    "        # [] * size = 构建长度为11的list\n",
    "        self.slots = [None] * self.size   # slots的列表用于存储键k  \n",
    "        self.data = [None] * self.size    # data的列表用于存储值v。\n",
    "    \n",
    "    def hashfunction(self,key,size):\n",
    "        return key%size\n",
    "    def rehash(self,oldhash,size):\n",
    "        return (oldhash+1)%size\n",
    "    \n",
    "    def put(self,key,data):\n",
    "        hashvalue = self.hashfunction(key,len(self.slots))\n",
    "        \n",
    "        if self.slots[hashvalue] == None:\n",
    "            self.slots[hashvalue]=key\n",
    "            self.data[hashvalue]=data\n",
    "        else:\n",
    "            \n",
    "            if self.slots[hashvalue]==key:\n",
    "                self.data[hashvalue]=data\n",
    "            else:\n",
    "                nextslot = self.rehash(hashvalue,len(self.slots))\n",
    "                while self.slots[nextslot] != None and self.slots[nextslot] !=  key:\n",
    "                    nextslot = self.rehash(nextslot,len(self.slots))\n",
    "                    if self.slots[nextslot]==None:\n",
    "                        self.slots[nextslot]=key\n",
    "                        self.data[nextslot]=data\n",
    "                    \n",
    "                \n",
    "                \n",
    "            \n",
    "# H = HashTable()            \n",
    "# key   54\n",
    "# data  \"cat\"\n",
    "# H[54] = \"cat\"   54%11 = 10  所以54会被放入slot十号槽（第11个槽）    \"cat\"会被放入data十号槽（第11个槽）\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e99b466a",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
